<!DOCTYPE html>
<html class="client-nojs vector-feature-night-mode-disabled vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-sticky-header-enabled" lang="en" dir="ltr"><head>
<meta charset="UTF-8">
<title>Driver scheduling problem</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="canonical" href="https://en.wikipedia.org/wiki/Driver_scheduling_problem"> <link href="./mw/ext.cite.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/user.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link rel="stylesheet" type="text/css" href="./mw/site.styles.css">
<link rel="stylesheet" type="text/css" href="./mw/noscript.css">
<link rel="stylesheet" type="text/css" href="./footer.css">
<link rel="stylesheet" type="text/css" href="./vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Driver_scheduling_problem rootpage-Driver_scheduling_problem skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading">
<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Driver scheduling problem</span></span>
</h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><p>The <b>driver scheduling problem</b> (DSP) is type of problem in <a href="Operations_research" title="Operations research">operations research</a> and <a href="Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a>.
</p><p>The DSP consists of selecting a set of duties (assignments) for the drivers or pilots of vehicles (e.g., buses, trains, boats, or planes) involved in the transportation of passengers or goods,<sup id="cite_ref-VoßDaduna2001_1-0" class="reference"><a href="#cite_note-VoßDaduna2001-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Salvendy2001_2-0" class="reference"><a href="#cite_note-Salvendy2001-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> within the constraints of various legislative and logistical criteria.
</p>
<div class="mw-heading mw-heading2"><h2 id="Criteria_and_modelling">Criteria and modelling</h2></div>
<p>This very complex problem involves several constraints related to labour and company rules and also different evaluation criteria and objectives. Being able to solve this problem efficiently can have a great impact on costs and quality of service for public transportation companies.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> There is a large number of different rules that a feasible duty might be required to satisfy, such as
</p>
<ul><li>Minimum and maximum stretch duration</li>
<li>Minimum and maximum break duration</li>
<li>Minimum and maximum work duration</li>
<li>Minimum and maximum total duration</li>
<li>Maximum extra work duration</li>
<li>Maximum number of vehicle changes</li>
<li>Minimum driving duration of a particular vehicle</li></ul>
<p><a href="Operations_research" title="Operations research">Operations research</a> has provided <a href="Optimization" class="mw-redirect" title="Optimization">optimization</a> models and <a href="Algorithm" title="Algorithm">algorithms</a> that lead to efficient solutions for this problem. Among the most common models proposed to solve the DSP are the <a href="Set_covering" class="mw-redirect" title="Set covering">Set Covering</a> and Set Partitioning Models (SPP/SCP).<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> In the SPP model, each work piece (task) is covered by only one duty. In the SCP model, it is possible to have more than one duty covering a given work piece.
In both models, the set of work pieces that needs to be covered is laid out in rows, and the set of previously defined feasible duties available for covering specific work pieces is arranged in columns. The DSP resolution, based on either of these models, is the selection of the set of feasible duties that guarantees that there is one (SPP) or more (SCP) duties covering each work piece while minimizing the total cost of the final schedule.
</p>
<div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2></div>
<ul><li><a href="Crew_scheduling" title="Crew scheduling">Crew scheduling</a></li>
<li><a href="Deadheading_(employee)" title="Deadheading (employee)">Deadheading (employee)</a></li></ul>
<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>
<style data-mw-deduplicate="TemplateStyles:r1239543626">
/* start https://en.wikipedia.org/ */
.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}
/* end https://en.wikipedia.org/ */
</style><div class="reflist">
<div class="mw-references-wrap"><ol class="references">
<li id="cite_note-VoßDaduna2001-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-VoßDaduna2001_1-0">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">
/* start https://en.wikipedia.org/ */
.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}
/* end https://en.wikipedia.org/ */
</style><cite id="CITEREFVoßDaduna2001" class="citation book cs1">Voß, Stefan; Daduna, Joachim R. (2001). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=RsvzwUiUBIsC&pg=PA122"><i>Computer Aided Scheduling of Public Transport</i></a>. Springer. pp. 122–. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783540422433</bdi><span class="reference-accessdate">. Retrieved <span class="nowrap">22 May</span> 2013</span>.</cite></span>
</li>
<li id="cite_note-Salvendy2001-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-Salvendy2001_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFSalvendy2001" class="citation book cs1">Salvendy, Gavriel (2001-05-25). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=sjY3IZ9Unv0C&pg=PA813"><i>Handbook of Industrial Engineering: Technology and Operations Management</i></a>. John Wiley & Sons. pp. 813–. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780471330578</bdi><span class="reference-accessdate">. Retrieved <span class="nowrap">22 May</span> 2013</span>.</cite></span>
</li>
<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFBorndörferMartin_GrötschelMarc_E._Pfetsch2006" class="citation journal cs1">Borndörfer, Ralf; <a href="Martin_Gr%C3%B6tschel" title="Martin Grötschel">Martin Grötschel</a>; Marc E. Pfetsch (2006). <a rel="nofollow" class="external text" href="http://www.orms-today.org/orms-4-06/frtransport.html">"Public transport to the fORe"</a>. <i>OR/MS Today</i>. <b>33</b> (2): <span class="nowrap">30–</span>40.</cite></span>
</li>
<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFLourençoPaixão,_J.P.Portugal,_R.2009" class="citation journal cs1">Lourenço, H.R.; Paixão, J.P.; Portugal, R. (2009). "Driver Scheduling Problem Modelling". <i>Public Transport: Planning and Operations</i>. <b>1</b> (2): <span class="nowrap">103–</span>120. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs12469-008-0007-0">10.1007/s12469-008-0007-0</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/10230%2F303">10230/303</a></span>.</cite></span>
</li>
<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFLourençoPaixão,_J.P.Portugal,_R.2001" class="citation journal cs1">Lourenço, H.R.; Paixão, J.P.; Portugal, R. (2001). <a rel="nofollow" class="external text" href="http://www.econ.upf.edu/en/research/onepaper.php?id=547">"The crew-scheduling module in the GIST system"</a>. <i>Economic Working Papers Series, Department of Economics and Business, Universitat Pompeu Fabra</i>. <b>547</b>.</cite></span>
</li>
</ol></div></div></div><!--htdig_noindex--><div><div class="zim-footer">
This article is issued from <a class="external text" title="Last edited on 2022-03-02" href="https://en.wikipedia.org/wiki/?title=Driver_scheduling_problem&oldid=1074901821">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
</body></html>